package com.xmg.dataStructure.search;

/**
 * 插值查找，适用于数组元素分布比较均匀的情况
 * 关键点：通过数值比例找到坐标插值，快速定位
 * int mid = (findVal-arr[left])/(arr[right]-arr[left])*(right-left)+left;
 */
public class InsertSearch {
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,23};
        int res = insertSearch(arr,0,arr.length-1,11);
        System.out.println(res);
    }

    public static int insertSearch(int[] arr,int left,int right,int findVal){
        if(left>right || findVal<arr[0] || findVal>arr[arr.length-1]){
            return -1;
        }
        int mid = (findVal-arr[left])/(arr[right]-arr[left])*(right-left)+left;
        int midValue = arr[mid];

        if(findVal>midValue){
            return insertSearch(arr,mid+1,right,findVal);
        }else if(findVal < midValue){
            return insertSearch(arr,left,mid-1,findVal);
        }else{
            return mid;
        }
    }
}
